GoogleDP: Differentially Private SQL with Bounded User Contribution

Differentially Private SQL with Bounded User Contribution

Royce J Wilson, Celia Yuxin Zhang, William Lam, Damien Desfontaines, Daniel Simmons-Marengo, Bryant Gipson

Video

GitHub https://github.com/google/differential-privacy

差分プライバシーとは

Differential Privacy: A Sound Way to Protect Private Data | Immuta

sensitivity

1 つの行が分析に与える影響の範囲を示す数値的尺度

how much a query's output changes when a row is added or removed in the database

sensitivityを制限すると、Laplace メカニズムを使用してクエリの出力にノイズを追加し差分プライバシー

laysakura.icon ちょいと日本語が変かも？

cipepser.icon ラプラス変換のラプラスさん

https://ja.wikipedia.org/wiki/ラプラス分布

Bounded User Contribution

Differential privacy requires some bound on maximum number of contributions each user can make to a single aggregation.

upper boundが高すぎるとノイズが大きく、

lower boundが低すぎるとデータが失われる

べスプラ：いくつかの外れ値のみが修正されるようにupper boundをできるだけ小さくする

差分プライバシーがないクエリ例

あるページに対するbrowser_agentごとのアクセスログをクエリする例を考える

アクセスログのそれぞれのレコードはcountsにせいぜい１しか影響与えない

Laplace Mechanismを使える

The sensitivity of a function f is the amount f’s output changes when its input changes by 1.

code:naive.sql

SELECT browser_agent, COUNT(*) AS visits FROM access_logs GROUP BY browser_agent;

table:naive

browser_agent visits

Mozilla/5.0 1758

AppleWebKit/537.36 1425

Chrome/77.0 3827

Mozilla/1.22 1

単一ユーザーによる複数のcontributions問題

通常のアプローチ：それぞれのカウントにノイズを加える

1/ε Laplace noise

加えて、今回のようなケースでは、特定のbrowser agentで同じユーザーが複数回閲覧しうるので、特定のGROUP BYパーティションのvisitsに任意の数のrowが加わりうる。つまり、query sensitivityが１である仮定に反する。

上記のナイーブなアプローチは、それぞれのパーティションにおいてユーザーはunbounded sensitivityである。

visitsにおいて、rowをカウントするのではなくuser-global sensitivityが１となるように異なるユーザーをカウントする。

つまり、単一ユーザーの複数回アクセスのデータを全て削ぎ落としたいわけではなく、query sensitivityが１である仮定を満たしたいので、最もアクセスしているユーザーによる影響を１にする。

nrryuya.icon > このセクションは、普通こうするという背景

code:contribution-bounding+noise.sql

SELECT broweser_agent, COUNT(DISTINCT uid) + Laplace(1/ε) AS visits

FROM access_logs

GROUP BY browser_agent

table:contribution-bounding+noise

browser_agent visits

Mozilla/5.0 1756

AppleWebKit/537.36 1423

Chrome/77.0 3828

Mozilla/1.22 2

row ownership

テーブル作成時にある特定のカラムにuser idを明示的に指定し、それぞれの行はそのユーザーが所有しているものとして、boundsを設ける

user-level DP

code:row-owenership.sql

CREATE TABLE access_logs(

username STRING,

browser_agent STRING,

) OPTIONS (uid_column = 'username');

cipepser.icon 全然わかってないんですが、クエリごとにboundsを満たすようなテーブルを作る必要がある？ユーザ重複を排したいというモチベはわかるものの、このテーブルをがあることで差分プライバシーを満たせるという理解でいいのかわからず...。ノイズの影響を高々1にしたい？

GROUP BYキーによる漏洩問題

攻撃者が1つのレコードが異なる二つのデータセットの識別を試みようとするケースに置いて、そのレコードが一方のデータベースだけに存在する場合、COUNTのノイズに関係なく、GROUP BYキーによる識別可能性。

シンプルに、を加えたCOUNTがあるτ閾値より低い場合、そのキーに紐づく結果をdrop。

Releasing Search Queries and Clicks Privately

これにより、(ε,δ)-DP with δ > 0

十分に高い τ であれば、十分高い確率でキーの識別可能性を十分小さくできる

glassonion1.icon 外れ値から攻撃を仕掛けるみたいなことですか

code: thresholding.sql

SELECT browser_agent, COUNT(DISTINCT uid) + Laplace(1/ε) AS visits

FROM access_logs

GROUP BY browser_agent

HAVING visits >= τ

table:thresholding

browser_agent visits

Mozilla/5.0 1756

AppleWebKit/537.36 1423

Chrome/77.0 3828

単一ユーザーによる複数のパーティションに対する複数のcontributions問題

ある個人が複数のブラウザで複数回アクセスした場合、query sensitivityがunboundedになる。

それぞれのユーザーに対して$ Cuを割り当て、ランダムに$ Cuパーティションだけ残し、他のパーティションのcontributionはドロップすることで、global sensitivityをboundにすることができる。

それぞれのユーザーは最大$ Cu countsの影響を与えるので、 $ C_u/ε Laplace noiseを使う。

code:contribution-bounding-across-partitions.sql

SELECT browser_agent, COUNT(DISTINCT uid) + Laplace(Cu/ε) AS visits

FROM (SELECT browser_agent, uid

FROM access_logs

GROUP BY browser_agent, uid)

TABLESAMPLE RESERVOIR // supports partitioning and reservoir sampling

(Cu ROWS PARTITION BY uid)

GROUP BY browser_agent

HAVING visits >= τ

より簡単なsyntaxを定義

code:anonymization-extension.sql

SELECT WITH ANONYMIZATION OPTIONS(epsilon=0.1, delta=1e-12)

browser_agent,

ANON_COUNT(* CLAMPED BETWEEN 0 AND 1) AS visits // global sensitivity

FROM access_logs

GROUP BY browser_agent;

Differential Privacy for Complex Data: Answering Queries Across Multiple Data Tables | NIST

Since the sensitivity of queries in this setting depends on the data itself, it can be difficult to bound the sensitivity, and the noise required to ensure differential privacy can be very high, leaving us with useless results.

まとめ

row ownershipというconceptを用いたuser-level差分プライバシーを定式化&production-levelでの実装

user-level DP

他にも、

精度分析のための実験用ツール

プライバシーを損なっていないかテストするフレームワーク

精度を最大限にするboundsを自動で計算

APPROX_BOUNDS(col)

Related work

PINQ, Flex

partition selection

Differentially private partition selection

https://colab.research.google.com/github/google/differential-privacy/blob/main/common_docs/partition_selection_playground.ipynb#scrollTo=1-UTSWYmfq6i

https://github.com/google/differential-privacy/blob/main/common_docs/partition_selection.md

Differential Privacy Accounting

https://github.com/google/differential-privacy/tree/main/python

code:res

❯❯ python dp_accounting/privacy_loss_distribution_basic_example.py

An algorithm that executes the Laplace Mechanism with parameter 3 for a total of 40 times is (10, 1.9236339299597314e-06)-DP.

An algorithm that executes the Laplace Mechanism with parameter 3 for a total of 40 times and in addition executes once the Gaussian Mechanism with STD 5 is (10, 2.4116135886755283e-06)-DP.

参考資料

CS6781 Lecture 25: Differential Privacy

An brief tour of Differential Privacy

Differential Privacy for Complex Data: Answering Queries Across Multiple Data Tables | NIST

Differential Privacy — Noise adding Mechanisms | by shaistha fathima | Becoming Human: Artificial Intelligence Magazine

Almost differential privacy - Ted is writing things

Google Basic DP Building Blocks LibraryのLaplaceとGaussianメカニズムにおけるノイズ生成のアルゴリズム

https://github.com/google/differential-privacy/blob/main/common_docs/Secure_Noise_Generation.pdf

appendix

ノイズメカニズム

Laplace Mechanism

シンプル、sensitivity